package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.List;
import java.util.Map;

/**
 * Kruskal 算法求最小生成树
 * 基本思路：按照权值从小到大选择 n - 1 条边，并保证这 n - 1 条边不产生回路
 * 难点：判断添加一个边之后有没有产生回路，将入的一个个边的两个点点是不是指向同一个终点
 *
 * @author zjj_admin
 * @date 2023/1/2 16:57
 */
public class KruskalAlgorithm {

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][]{
                {-1, 12, -1, -1, -1, 16, 14},
                {12, -1, 10, -1, -1, 7, -1},
                {-1, 10, -1, 3, 5, 6, -1},
                {-1, -1, 3, -1, 4, -1, -1},
                {-1, -1, 5, 4, -1, 2, 8},
                {16, 7, 6, -1, 2, -1, 9},
                {14, -1, -1, -1, 8, 9, -1}
        };

//        int[][] weight = new int[][]{
//                {-1, 9, -1, -1, -1, 5, 8},
//                {9, -1, 6, -1, -1, 3, -1},
//                {-1, 6, -1, 4, 2, 8, -1},
//                {-1, -1, 4, -1, 12, -1, -1},
//                {-1, -1, 2, 12, -1, 3, 12},
//                {5, 3, -1, 8, 3, -1, 10},
//                {8, -1, -1, -1, 12, 10, -1}
//        };

        int vertex = data.length;
        Graph graph = new Graph(vertex);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, vertex, data, weight);
        //显示图
        minTree.showGraph(graph);
        int shortestPath = 0;
        List<GraphPath> res = minTree.kruskal(graph);
        for (GraphPath re : res) {
            shortestPath += re.length;
        }
        System.out.println("res = " + res);
        System.out.println("shortestPath = " + shortestPath);


        Map<String, Object> res1 = minTree.prime(graph, 0);
        List<String> paths1 = (List<String>) res1.get("paths");
        Integer shortestPath1 = (Integer) res1.get("shortestPath");
        System.out.println("shortestPath1 = " + shortestPath1);
        System.out.println("paths1 = " + paths1);

    }
}
